package com.cango.student.algorithm.leetcode;

import com.cango.student.algorithm.NodeSort;
import com.cango.student.algorithm.nodepackage.Node;

/**
 * reverse-linked-list
 */
public class Reversal {
    /**
     * 链表反转
     */
    public static Node reversal(Node node) {
        if (node == null || node.next == null) {
            return node;
        } else {
            // 返回最后的node
            Node header = reversal(node.next);
            node.next.next = node;
            node.next = null;
            return header;
        }
    }

    /**
     * 链表反转
     */
    public static Node reversal2(Node node) {
        if (node == null) return null;

        Node pre = node;
        Node cur = node.next;
        Node next;
        while (cur != null) {
            next = cur.next;

            cur.next = pre;

            pre = cur;
            cur = next;
        }

        node.next = null;
        return pre;
    }


    public static void main(String[] args) {
        Node linkNode1 = new Node();
        linkNode1.data = 1;
        Node linkNode2 = new Node();
        linkNode2.data = 2;
        Node linkNode3 = new Node();
        linkNode3.data = 3;
        Node linkNode4 = new Node();
        linkNode4.data = 4;
        Node linkNode5 = new Node();
        linkNode5.data = 5;
        Node linkNode6 = new Node();
        linkNode6.data = 6;

        linkNode1.next = linkNode2;
        linkNode2.next = linkNode3;
        linkNode3.next = linkNode4;
        linkNode4.next = linkNode5;
        linkNode5.next = linkNode6;
        reversal2(linkNode1);

        System.out.println(linkNode6.next.next.next.next.next.data);
    }
}
